package club.xiaojiawei.hash;

import java.util.HashMap;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 4/29/22 2:41 PM
 * @question 454.四数相加II
 * @description 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
 * 0 <= i, j, k, l < n
 * nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
 */
public class FourSumCountII454 {

    public static void main(String[] args) {
        int[] num1 = {1, 2};
        int[] num2 = {-2, -1};
        int[] num3 = {-1, 2};
        int[] num4   = {0, 2};
        int result = fourSumCount(num1, num2, num3, num4);
        System.out.println(result);
    }

    /**
     * HashMap+二分
     * 将四个数组和为0的问题化为两个数组的和为0的问题，从而将四层for简化成两个两层for,时间复杂度从n的四次方变成n的平方
     * @param nums1
     * @param nums2
     * @param nums3
     * @param nums4
     * @return
     */
    public static int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int k : nums1) {
            for (int i : nums2) {
                map.put(k + i, map.getOrDefault(k + i, 0) + 1);
            }
        }
        int amount = 0;
        for (int k : nums3) {
            for (int i : nums4) {
                if (map.containsKey(-k - i)) {
                    amount += map.get(-k - i);
                }
            }
        }
        return amount;
    }

    /**
     * 暴力解法
     * 四层for
     * @param nums1
     * @param nums2
     * @param nums3
     * @param nums4
     * @return
     */
    public static int fourSumCount2(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0;
        int amount = 0;
        for (int o = 0; o < nums1.length; o++) {
            count += nums1[o];
            for (int t = 0; t < nums2.length; t++) {
                count += nums2[t];
                for (int h = 0; h < nums3.length; h++) {
                    count += nums3[h];
                    for (int f = 0; f < nums4.length; f++) {
                        if (count + nums4[f] == 0){
                            amount++;
                        }
                    }
                    count -= nums3[h];
                }
                count -= nums2[t];
            }
            count -= nums1[o];
        }
        return amount;
    }

}
